#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;


class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        int n = nums.size();
        while (fast < n)
        {
            if (nums[fast] != 0)
            {
                swap(nums[fast], nums[slow]);
                slow++;
            }
            fast++;
        }
    }
};

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        vector<int> ret(n);
        int fast = 0;
        int slow = 0;
        while (fast < n)
        {
            if (arr[slow] == 0)
            {
                ret[fast++] = 0;
                if (fast == n)
                {
                    break;
                }
                ret[fast++] = 0;
            }
            else
            {
                ret[fast++] = arr[slow];
            }
            slow++;
        }
        for (int i = 0; i < n; i++)
        {
            arr[i] = ret[i];
        }
    }
};

class Solution {
public:
    int num(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = num(n);
        while (slow != fast)
        {
            slow = num(slow);
            fast = num(num(fast));
        }
        return slow == 1 ? true : false;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0;
        int right = n - 1;
        int my_max = 0;
        while (right > left)
        {
            my_max = max(min(height[left], height[right]) * (right - left), my_max);
            if (height[left] > height[right])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return my_max;
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int right = n - 1;
        int ret = 0;
        while (right > 1)
        {
            int left = 0;
            int mid = right - 1;
            while (left < mid)
            {
                if (nums[left] + nums[mid] > nums[right])
                {
                    ret += (mid - left);
                    mid--;
                }
                else
                {
                    left++;
                }
            }
            right--;
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0;
        int right = price.size() - 1;
        while (left < right)
        {
            if (price[left] + price[right] > target)
            {
                right--;
            }
            else if (price[left] + price[right] < target)
            {
                left++;
            }
            else
            {
                break;
            }
        }
        vector<int> ret;
        ret.push_back(price[left]);
        ret.push_back(price[right]);
        return ret;
    }
};